package tanxin;

import java.util.Arrays;
import java.util.Comparator;

public class leetCode1005_largestSumAfterKNegations {
    public static void main(String[] args) {
        leetCode1005_largestSumAfterKNegations a = new leetCode1005_largestSumAfterKNegations();
        int[] nums = {-2,9,9,8,4};
        int i = a.largestSumAfterKNegations2(nums, 5);
        System.out.println(i);
    }
    public int largestSumAfterKNegations(int[] nums, int k) {
        int sum = 0;
        if(nums.length == 0) return 0;
        int minIndex = 0;
        Arrays.sort(nums);
       while (k > 0){
           nums[minIndex] = -nums[minIndex];
           //只有后面元素存在且小于当前元素时，更新最小元素的索引
           //对于有负数的情况会先把负数求反，对于正数的话，始终对最小的改变
            if(minIndex + 1 < nums.length && nums[minIndex + 1] < nums[minIndex]){
                minIndex++;
            }
            k--;
        }
        for (int num : nums) {
            sum+=num;
        }
        return sum;
    }

    public int largestSumAfterKNegations2(int[] nums, int k) {
        int sum = 0;
        Integer[] arr = Arrays.stream(nums).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Math.abs(o2) - Math.abs(o1);
            }
        });
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] < 0 && k > 0){
                arr[i] = -arr[i];
                k--;
            }
        }
        while (k > 0){
            arr[arr.length - 1] = - arr[arr.length - 1];
            k--;
        }
        for (Integer integer : arr) {
            sum += integer;
        }
        return sum;
    }
}
